{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #XOR Queries of a Subarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: xorQueries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子数组异或查询"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个正整数数组 <code>arr</code>，现给你一个对应的查询数组 <code>queries</code>，其中 <code>queries[i] = [L<sub>i, </sub>R<sub>i</sub>]</code>。</p>\n",
    "\n",
    "<p>对于每个查询 <code>i</code>，请你计算从 <code>L<sub>i</sub></code> 到 <code>R<sub>i</sub></code> 的 <strong>XOR</strong> 值（即 <code>arr[L<sub>i</sub>] <strong>xor</strong> arr[L<sub>i</sub>+1] <strong>xor</strong> ... <strong>xor</strong> arr[R<sub>i</sub>]</code>）作为本次查询的结果。</p>\n",
    "\n",
    "<p>并返回一个包含给定查询 <code>queries</code> 所有结果的数组。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]\n",
    "<strong>输出：</strong>[2,7,14,8] \n",
    "<strong>解释：</strong>\n",
    "数组中元素的二进制表示形式是：\n",
    "1 = 0001 \n",
    "3 = 0011 \n",
    "4 = 0100 \n",
    "8 = 1000 \n",
    "查询的 XOR 值为：\n",
    "[0,1] = 1 xor 3 = 2 \n",
    "[1,2] = 3 xor 4 = 7 \n",
    "[0,3] = 1 xor 3 xor 4 xor 8 = 14 \n",
    "[3,3] = 8\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [4,8,2,10], queries = [[2,3],[1,3],[0,0],[0,3]]\n",
    "<strong>输出：</strong>[8,0,4,4]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= arr.length <= 3 * 10^4</code></li>\n",
    "\t<li><code>1 <= arr[i] <= 10^9</code></li>\n",
    "\t<li><code>1 <= queries.length <= 3 * 10^4</code></li>\n",
    "\t<li><code>queries[i].length == 2</code></li>\n",
    "\t<li><code>0 <= queries[i][0] <= queries[i][1] < arr.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [xor-queries-of-a-subarray](https://leetcode.cn/problems/xor-queries-of-a-subarray/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [xor-queries-of-a-subarray](https://leetcode.cn/problems/xor-queries-of-a-subarray/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,4,8]\\n[[0,1],[1,2],[0,3],[3,3]]', '[4,8,2,10]\\n[[2,3],[1,3],[0,0],[0,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        for i in range(1,len(arr)):arr[i]^=arr[i-1]\n",
    "        for i in range(len(queries)):queries[i]=arr[queries[i][1]] ^ (arr[queries[i][0]-1] if queries[i][0] else 0)\n",
    "        return queries"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        xors=[0]\n",
    "\n",
    "        for num in arr:\n",
    "            xors.append(xors[-1] ^ num)\n",
    "        \n",
    "\n",
    "        ans = list()\n",
    "\n",
    "        for left, right in queries: \n",
    "            ans.append(xors[left] ^ xors[right + 1])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        for i in range(1,len(arr)):arr[i]^=arr[i-1]\n",
    "        return [(arr[i-1] if i else 0)^arr[j] for i,j in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        prefix=[0]\n",
    "        for n in arr:\n",
    "            prefix.append(prefix[-1]^n)\n",
    "        return [prefix[j+1]^prefix[i] for i,j in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n=len(arr)\n",
    "        s=[0]*(n+1)\n",
    "        for i in range(1,n+1):\n",
    "            if i==1:\n",
    "                s[i]=arr[i-1]\n",
    "            else:\n",
    "                s[i]=s[i-1]^arr[i-1]\n",
    "        ret=[]\n",
    "        for i in range(len(queries)):\n",
    "            ret.append(s[queries[i][1]+1]^s[queries[i][0]])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        prex = [0]; t = 0\n",
    "        for x in arr:\n",
    "            t = t^x\n",
    "            prex+= t,\n",
    "        return [prex[a]^prex[b+1] for a, b in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "\n",
    "        xors=[0]\n",
    "\n",
    "        for num in arr:\n",
    "            xors.append(xors[-1] ^ num)\n",
    "        \n",
    "\n",
    "        ans = list()\n",
    "\n",
    "        for left, right in queries: \n",
    "            ans.append(xors[left] ^ xors[right + 1])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 前缀和\n",
    "        prefix = [arr[0]]\n",
    "        for n in arr[1:]:\n",
    "            prefix.append(prefix[-1] ^ n)\n",
    "        prefix.append(0)\n",
    "        return [prefix[l-1] ^ prefix[r] for l, r in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(arr)\n",
    "        for i in range(1, n):\n",
    "            arr[i] ^= arr[i-1]\n",
    "\n",
    "        for q in queries:\n",
    "            if q[0] == 0:\n",
    "                ans.append(arr[q[1]])\n",
    "            else:\n",
    "                ans.append(arr[q[1]] ^ arr[q[0]-1])\n",
    "            \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 前缀和\n",
    "        prefix = [0]\n",
    "        for n in arr:\n",
    "            prefix.append(prefix[-1] ^ n)\n",
    "        return [prefix[l] ^ prefix[r+1] for l, r in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        \n",
    "        ans=[0]*len(queries)\n",
    "        for i in range(1,len(arr)):\n",
    "            arr[i]=arr[i]^arr[i-1]\n",
    "        for i in range(len(queries)):\n",
    "            if queries[i][0]>0:\n",
    "                ans[i]=arr[queries[i][1]]^arr[queries[i][0]-1]\n",
    "            else:\n",
    "                ans[i]=arr[queries[i][1]]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 暴力---超时是肯定的\n",
    "        # n = len(arr)\n",
    "        # ans = []\n",
    "        # for l, r in queries:\n",
    "        #     tm = 0\n",
    "        #     for i in range(l, r+1, 1):\n",
    "        #         tm = tm^arr[i]\n",
    "        #     ans.append(tm)\n",
    "        # return ans\n",
    "\n",
    "\n",
    "        # 异或和\n",
    "        n = len(arr)\n",
    "        pre_sum = [arr[0]]*n\n",
    "        for i in range(1, n):\n",
    "            pre_sum[i] = pre_sum[i-1]^arr[i]\n",
    "        ans = []\n",
    "        for l, r in queries:\n",
    "            if l > 0:\n",
    "                ans.append(pre_sum[l-1]^pre_sum[r])\n",
    "            else:\n",
    "                ans.append(pre_sum[r])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        state = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            state[i + 1] = state[i] ^ arr[i]\n",
    "            pass\n",
    "        res = []\n",
    "\n",
    "        for x, y in queries:\n",
    "            res.append(state[y + 1] ^ state[x])\n",
    "            pass\n",
    "        return res\n",
    "\n",
    "    pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 前缀和\n",
    "        prefix_sum = [arr[0] for _ in range(len(arr))]\n",
    "        # prefix_sum[0] = arr[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            prefix_sum[i] = prefix_sum[i-1] ^ arr[i]\n",
    "        res = [0 for _ in range(len(queries))]\n",
    "        for i in range(len(queries)):\n",
    "            left, right = queries[i]\n",
    "            if left == 0:\n",
    "                res[i] = prefix_sum[right]\n",
    "            else:\n",
    "                res[i] = prefix_sum[right] ^ prefix_sum[left - 1]\n",
    "        \n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        ans = [0]\n",
    "        for num in arr:\n",
    "            ans.append(ans[-1] ^ num)\n",
    "        res = []\n",
    "        for a, b in queries:\n",
    "            res.append(ans[b+1] ^ ans[a])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        pre = [0]\n",
    "        for val in arr:\n",
    "            pre.append(xor(val, pre[-1]))\n",
    "        print(pre)\n",
    "        return [xor(pre[x], pre[y + 1]) for x, y in queries]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class NumArray:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums = nums\n",
    "        self.tree = [0] * (len(nums) + 1)\n",
    "        for i, num in enumerate(nums, 1):\n",
    "            self.add(i, num)\n",
    "\n",
    "    def add(self, index: int, val: int):\n",
    "        while index < len(self.tree):\n",
    "            self.tree[index] ^= val\n",
    "            index += index & -index\n",
    "\n",
    "    def prefixSum(self, index) -> int:\n",
    "        s = 0\n",
    "        while index:\n",
    "            s ^= self.tree[index]\n",
    "            index -= index & -index\n",
    "        return s\n",
    "\n",
    "    def sumRange(self, left: int, right: int) -> int:\n",
    "        return self.prefixSum(right + 1) ^ self.prefixSum(left)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        q_len = len(queries)\n",
    "        res = [0]*q_len\n",
    "        na = NumArray(arr)\n",
    "        for i in range(q_len):\n",
    "            l,r = queries[i]\n",
    "            res[i] = na.sumRange(l, r)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 前缀和\n",
    "        prefix_sum = [arr[0] for _ in range(len(arr))]\n",
    "        # prefix_sum[0] = arr[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            prefix_sum[i] = prefix_sum[i-1] ^ arr[i]\n",
    "        res = [0 for _ in range(len(queries))]\n",
    "        for i in range(len(queries)):\n",
    "            left, right = queries[i]\n",
    "            if left == 0:\n",
    "                res[i] = prefix_sum[right]\n",
    "            else:\n",
    "                res[i] = prefix_sum[right] ^ prefix_sum[left - 1]\n",
    "        \n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        #前缀和 变体  异或和?\n",
    "        #可以用那个 reduce? reduce只有最后解  需要个类似accumulate的函数\n",
    "        prex = [0]\n",
    "        t = 0\n",
    "        for x in arr:\n",
    "            t = t^x\n",
    "            prex+= t,\n",
    "        # print(prex)\n",
    "        ans = []\n",
    "        for a, b in queries:\n",
    "            ans += prex[a]^prex[b+1],\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        prefixsum = [0] * n\n",
    "        prefixsum[0] = arr[0]\n",
    "        for i in range(1,n):\n",
    "            prefixsum[i] = prefixsum[i-1] ^ arr[i]\n",
    "        ans = []\n",
    "        for query in queries:\n",
    "            if query[0] >= 1:\n",
    "                ans.append(prefixsum[query[0]-1] ^ prefixsum[query[1]])\n",
    "            else:\n",
    "                ans.append(prefixsum[query[1]])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 前缀和\n",
    "        prefix_sum = [arr[0] for _ in range(len(arr))]\n",
    "        for i in range(1, len(arr)):\n",
    "            prefix_sum[i] = prefix_sum[i-1] ^ arr[i]\n",
    "        res = [0 for _ in range(len(queries))]\n",
    "        for i in range(len(queries)):\n",
    "            left, right = queries[i]\n",
    "            if left == 0:\n",
    "                res[i] = prefix_sum[right]\n",
    "            else:\n",
    "                res[i] = prefix_sum[right] ^ prefix_sum[left - 1]\n",
    "        \n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        xors = [0]\n",
    "        for num in arr:\n",
    "            xors.append(xors[-1] ^ num)\n",
    "        ans = []\n",
    "        for left, right in queries:\n",
    "            ans.append(xors[left] ^ xors[right + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        dp = [None for _ in range(len(arr))]\n",
    "        temp_rst = 0\n",
    "        results = []\n",
    "\n",
    "        for i, n in enumerate(arr):\n",
    "            temp_rst = n ^ temp_rst\n",
    "            dp[i] = temp_rst\n",
    "\n",
    "        for start, end in queries:\n",
    "            prev_rst = dp[start - 1] if start > 0 else 0\n",
    "            results.append(dp[end] ^ prev_rst)\n",
    "\n",
    "        return results\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        xors = [0]\n",
    "        for num in arr:\n",
    "            xors.append(xors[-1] ^ num)\n",
    "        \n",
    "        ans = list()\n",
    "        for left, right in queries:\n",
    "            ans.append(xors[left] ^ xors[right + 1])\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums = arr\n",
    "        pre = [0]\n",
    "        for v in nums:\n",
    "            pre.append(pre[-1] ^ v)\n",
    "        res =[]\n",
    "        for l, r in queries:\n",
    "            res.append(pre[l]^pre[r + 1])\n",
    "        return res\n",
    "    \n",
    "        # res = []\n",
    "        # for i,j in queries:\n",
    "        #     tmp = arr[i]\n",
    "        #     for v in range(i+1, j):\n",
    "        #         tmp = tmp ^ arr[v]\n",
    "        #     # if i != j:\n",
    "        #     #     res.append(arr[i] ^ arr[j])\n",
    "        #     # else:\n",
    "        #     #     res.append(arr[i])\n",
    "        #     res.append(tmp)\n",
    "        # return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 前缀和\n",
    "        prefix_sum = [0 for _ in range(len(arr))]\n",
    "        prefix_sum[0] = arr[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            prefix_sum[i] = prefix_sum[i-1] ^ arr[i]\n",
    "        res = [0 for _ in range(len(queries))]\n",
    "        for i in range(len(queries)):\n",
    "            left, right = queries[i]\n",
    "            if left == 0:\n",
    "                res[i] = prefix_sum[right]\n",
    "            else:\n",
    "                res[i] = prefix_sum[right] ^ prefix_sum[left - 1]\n",
    "        \n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        prex = [0]; t = 0\n",
    "        for x in arr:\n",
    "            t = t^x\n",
    "            prex+= t,\n",
    "        return [prex[a]^prex[b+1] for a, b in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        xors = [0]\n",
    "        for num in arr:\n",
    "            xors.append(xors[-1] ^ num)\n",
    "        \n",
    "        ans = list()\n",
    "        for left, right in queries:\n",
    "            ans.append(xors[left] ^ xors[right + 1])\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        xnor=lambda a,b: ~a^b\n",
    "        s=[0]*(len(arr)+1)\n",
    "        for i,x in enumerate(arr):\n",
    "            s[i+1]=s[i]^arr[i]\n",
    "        ans=[0]*len(queries)\n",
    "        for i,querie in enumerate(queries):\n",
    "            ans[i]=s[querie[1]+1]^s[querie[0]]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        perx =[0] ; t=0\n",
    "        for x in arr:\n",
    "            t = t^x\n",
    "            perx += t,\n",
    "\n",
    "        return [perx[a]^perx[b+1] for a,b in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import itertools\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        all_xor = list(itertools.accumulate([0] + arr, operator.xor))\n",
    "        return [all_xor[i] ^ all_xor[j + 1] for i,j in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        sums = [0]\n",
    "        n = len(arr)\n",
    "        for i in range(1, n + 1):\n",
    "            sums.append(sums[i-1] ^ arr[i-1])\n",
    "        ret = []\n",
    "        for l, r in queries:\n",
    "            ret.append(sums[r+1] ^ sums[l])\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        res = []\n",
    "        n = len(arr)\n",
    "        pre = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            pre[i+1] = pre[i] ^ arr[i]\n",
    "        for a, b in queries:\n",
    "            res.append(pre[b+1] ^ pre[a])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        #异或的前缀性质,用到了异或运算的结合律\n",
    "        nums=[0]\n",
    "        for num in arr:\n",
    "            nums.append(num^nums[-1])\n",
    "        n=len(queries)\n",
    "        ans=[0]*n\n",
    "        for i in range(n):\n",
    "            x,y=queries[i]\n",
    "            ans[i]=nums[y+1]^nums[x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        dp = [0]\n",
    "        tmp = 0\n",
    "        for num in arr:\n",
    "            tmp = tmp ^ num\n",
    "            dp.append(tmp)\n",
    "        res = []\n",
    "        for query in queries:\n",
    "            res.append(dp[query[1] + 1] ^ dp[query[0]])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # res = []\n",
    "        # for query in queries:\n",
    "        #     cur = 0\n",
    "        #     for i in range(query[0], query[1] + 1):\n",
    "        #         cur = cur ^ arr[i]\n",
    "        #     res.append(cur)\n",
    "        # return res\n",
    "        xros = [0]\n",
    "        for num in arr:\n",
    "            xros.append(xros[-1] ^ num)\n",
    "        res = []\n",
    "        for left, right in queries:\n",
    "            res.append(xros[left] ^ xros[right + 1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        xors = [0]\n",
    "        for num in arr:\n",
    "            xors.append(xors[-1] ^ num)\n",
    "        ans = list()\n",
    "        for left, right in queries:\n",
    "            ans.append(xors[left] ^ xors[right + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        xorlist = []\n",
    "        now = 0\n",
    "        reslist = []\n",
    "        for item in arr:\n",
    "            xorlist.append(now^item)\n",
    "            now = now ^ item\n",
    "        # print(xorlist)\n",
    "        for query in queries:\n",
    "            if query[0] > 0:\n",
    "                reslist.append(xorlist[query[1]]^xorlist[query[0]-1])\n",
    "            else:\n",
    "                reslist.append(xorlist[query[1]])\n",
    "        return reslist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        pre=[0]\n",
    "        for a in arr:\n",
    "            pre.append(pre[-1]^a)\n",
    "        return [pre[r+1]^pre[l] for l,r in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        xorlist = []\n",
    "        now = 0\n",
    "        reslist = []\n",
    "        for item in arr:\n",
    "            xorlist.append(now^item)\n",
    "            now = now ^ item\n",
    "        print(xorlist)\n",
    "        for query in queries:\n",
    "            if query[0] > 0:\n",
    "                reslist.append(xorlist[query[1]]^xorlist[query[0]-1])\n",
    "            else:\n",
    "                reslist.append(xorlist[query[1]])\n",
    "        return reslist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        arr = [0] + arr\n",
    "        for i in range(1, len(arr)):\n",
    "            arr[i] ^= arr[i - 1]\n",
    "        res = []\n",
    "        for s, e in queries:\n",
    "            res.append(arr[e + 1] ^ arr[s])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        xor = [0]\n",
    "        tmp = 0\n",
    "        for i in range(n):\n",
    "            tmp ^= arr[i]\n",
    "            xor.append(tmp)\n",
    "        ans = []\n",
    "        for query in queries:\n",
    "            ans.append(xor[query[0]]^xor[query[1]+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        arr = list(itertools.accumulate(arr, xor)) \n",
    "        return [arr[j] ^ arr[i - 1] if i > 0 else arr[j] for i, j in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        nums=[0]\n",
    "        for num in arr:\n",
    "            nums.append(num^nums[-1])\n",
    "        n=len(queries)\n",
    "        ans=[0]*n\n",
    "        for i in range(n):\n",
    "            x,y=queries[i]\n",
    "            ans[i]=nums[y+1]^nums[x]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        len_arr = len(arr)\n",
    "        pre_xor = [0] * (len_arr + 1)\n",
    "\n",
    "        for i in range(1, len_arr + 1):\n",
    "            pre_xor[i] = pre_xor[i - 1] ^ arr[i - 1]\n",
    "\n",
    "        len_queries = len(queries)\n",
    "        res = [0] * len_queries\n",
    "\n",
    "        for j, one_query in enumerate(queries):\n",
    "            start_index = one_query[0]\n",
    "            end_index = one_query[1]\n",
    "            res[j] = pre_xor[start_index] ^ pre_xor[end_index + 1]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        result = []\n",
    "        cached = []\n",
    "\n",
    "        for i,v in enumerate(arr) :\n",
    "            if i == 0 :\n",
    "                cached.append(v)\n",
    "                continue\n",
    "                pass\n",
    "            cached.append(cached[-1] ^ v)\n",
    "            pass\n",
    "\n",
    "        for query in queries :\n",
    "            l = query[0]\n",
    "            r = query[1]\n",
    "            if l >= 1 :\n",
    "                v = cached[r] ^ cached[l-1]\n",
    "                pass\n",
    "            else:\n",
    "                v = cached[r]\n",
    "                pass\n",
    "            result.append(v)\n",
    "            pass\n",
    "\n",
    "        return result\n",
    "\n",
    "        pass\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class NumArray:\n",
    "    def __init__(self, nums: List[int]):\n",
    "        self.nums = nums\n",
    "        self.tree = [0] * (len(nums) + 1)\n",
    "        for i, num in enumerate(nums, 1):\n",
    "            self.add(i, num)\n",
    "\n",
    "    def add(self, index: int, val: int):\n",
    "        while index < len(self.tree):\n",
    "            self.tree[index] ^= val\n",
    "            index += index & -index\n",
    "\n",
    "    def prefixSum(self, index) -> int:\n",
    "        s = 0\n",
    "        while index:\n",
    "            s ^= self.tree[index]\n",
    "            index -= index & -index\n",
    "        return s\n",
    "\n",
    "    def update(self, index: int, val: int) -> None:\n",
    "        self.add(index + 1, val ^ self.nums[index])\n",
    "        self.nums[index] = val\n",
    "\n",
    "    def sumRange(self, left: int, right: int) -> int:\n",
    "        return self.prefixSum(right + 1) ^ self.prefixSum(left)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        q_len = len(queries)\n",
    "        res = [0]*q_len\n",
    "        na = NumArray(arr)\n",
    "        for i in range(q_len):\n",
    "            l,r = queries[i]\n",
    "            res[i] = na.sumRange(l, r)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        prefix = [0 for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            prefix[i] = prefix[i-1]^arr[i-1]\n",
    "        res = []\n",
    "        # print(prefix)\n",
    "        for l, r in queries:\n",
    "            res.append(prefix[r+1]^prefix[l])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        XORprex = [0 for _ in range(len(arr))]\n",
    "        XORprex[0] = arr[0]\n",
    "\n",
    "        for i in range(1, len(arr)):\n",
    "            XORprex[i] = XORprex[i-1] ^ arr[i]\n",
    "        \n",
    "        ans = []\n",
    "        for query in queries:\n",
    "            l, r = query[0], query[1]\n",
    "            if l == 0:\n",
    "                ans.append(XORprex[r])\n",
    "            else:\n",
    "                ans.append(XORprex[r] ^ XORprex[l-1])\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        xors = [0 for _ in range(n + 1)]\n",
    "        for i, num in enumerate(arr):\n",
    "            xors[i + 1] = xors[i] ^ num\n",
    "\n",
    "        ans = []\n",
    "        for left, right in queries:\n",
    "            ans.append( xors[left] ^ xors[right + 1] )\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        s = [0]\n",
    "        for x in arr:\n",
    "            s.append(s[-1] ^ x)\n",
    "        \n",
    "        res = []\n",
    "        for l, r in queries:\n",
    "            res.append(s[r + 1] ^ s[l])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        pre = [0]\n",
    "        for c in arr:\n",
    "            pre.append(pre[-1] ^ c)\n",
    "        ans = []\n",
    "        for l,r in queries:\n",
    "            ans.append(pre[r + 1] ^ pre[l])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # a ^ b = c，即 b = c ^ a\n",
    "        ans = []\n",
    "        # 构建前缀和\n",
    "        add = [0] * (len(arr) + 1)\n",
    "        for i in range(len(arr)):\n",
    "            add[i+1] = add[i] ^ arr[i]\n",
    "        \n",
    "        # query\n",
    "        for query in queries:\n",
    "            l = query[0]\n",
    "            r = query[1]\n",
    "            ans.append(add[r + 1] ^ add[l])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(arr)\n",
    "        cum = [0] * (n+1)\n",
    "        for i in range(1, n+1):\n",
    "            cum[i] = cum[i-1] ^ arr[i-1]\n",
    "            # print(bin(cum[i]))\n",
    "        ans = []\n",
    "        for s, e in queries:\n",
    "            ans.append(cum[s] ^ cum[e+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\r\n",
    "        #前缀xor\r\n",
    "        pre_xor = [0]\r\n",
    "        for num in arr:\r\n",
    "            pre_xor.append(pre_xor[-1] ^ num)\r\n",
    "        res = []\r\n",
    "        #[l, r] = [0, r] ^ [0, l - 1]\r\n",
    "        for l, r in queries:\r\n",
    "            res.append(pre_xor[r + 1] ^ pre_xor[l])\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        # 前缀和\n",
    "        prefix_sum = [arr[0] for _ in range(len(arr))]\n",
    "        for i in range(1, len(arr)):\n",
    "            prefix_sum[i] = prefix_sum[i-1] ^ arr[i]\n",
    "        res = [0 for _ in range(len(queries))]\n",
    "        for i, (left, right) in enumerate(queries):\n",
    "            if left == 0:\n",
    "                res[i] = prefix_sum[right]\n",
    "            else:\n",
    "                res[i] = prefix_sum[right] ^ prefix_sum[left - 1]\n",
    "        \n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def xorQueries(self, arr: List[int], queries: List[List[int]]) -> List[int]:\n",
    "        xors = [0]\n",
    "        for num in arr:\n",
    "            xors.append(xors[-1] ^ num)\n",
    "        \n",
    "        ans = list()\n",
    "        for left, right in queries:\n",
    "            ans.append(xors[left] ^ xors[right + 1])\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
